Міністерство освіти і науки УкраїниЛьвівський національний університет імені Івана Франка Звітпро виконання лабораторної роботи №4: «Особливості реалізації пошуку в глибину в графах»  Львів 2016 Завдання до роботи № 4. Тема роботи: Особливості реалізації пошуку в глибину у графах. Вихідні дані: Задано: – звичайний розгалужений граф (не менше 4-5и гілок) порядку 15-20 розміром 20-30; – початкова і цільова вершини графа; – напрям обходу. Завдання: – візуально представити заданий граф; – створити програму виконання пошуку на одній з мов програмування; – знайти найкоротший шлях до вказаної вершини, використовуючи алгоритм пошуку в глибину; – відмітити переваги і недоліки цього виду пошуку. Вимоги: У програмі передбачити: – можливість змінювати розмірність і порядок графа; – можливість змінювати напрям обходу графа; – зреалізувати візуалізацію процесу пошуку і його результатів. Теоретичні відомості Відповідно до використання евристичної інформації алгоритми діляться на два класи – сліпі та евристичні (спрямовані). У сліпих алгоритмах пошуку місцезнаходження в просторі цільової вершини ніяк не впливає на порядок, в якому розкриваються (перебираються) вершини. Сліпий метод має два види пошуку –пошук углиб і пошук вшир. При пошуку вширину на фіксованому рівні досліджуються всі альтернативи і лише після цього здійснюється перехід на наступний рівень. Метод може виявитися гіршим за метод пошуку вглибину, якщо в графі всі шляхи, що ведуть до цільової вершини, розташовані приблизно на одній і тій же глибині. При пошуку углибинукожна альтернатива досліджується до кінця, без урахування решти шляхів. Метод поганий для "високих" дерев, оскільки легко можна прослизнути мимо потрібної гілки і витратити багато зусиль на дослідження "порожніх" альтернатив. Метод перебору в глибину. При переборі в глибину насамперед слід розкривати ті вершини, які були побудовані останніми. Першою вершиною, що розкривається, є коренева. Процес завжди буде йти по крайній лівій (або правій – згідно з заданим напрямком обходу) гілці вершин. Щоб якось обмежити перебір, вводиться поняття глибини вершини в дереві перебору. Глибина кореня дерева дорівнює нулю, а глибина будь-якої наступної вершини дорівнює одиниці плюс глиби на вершини, що безпосередньо їй передує. Найбільшу глибину завжди буде мати та вершина, яка повинна бути в цей момент розкрита. Якщо шлях, який утворюється при пошуку, виявляється марним, тобто при заданій глибині розкриття цільової вершини не досягнуто, необхідно повернутися в попередню розкриту вершину і спробувати ще раз застосувати до неї операцію розкривання. І так до тих пір, поки не буде отримана цільова вершина. Повернення здійснюється за допомогою покажчиків. Як тільки в про-цесі породження вершин досягається задана гранична глибина, розкривається вершина найбільшої глибини, що не перевищує цієї межі. Порядок обходу вершин графа проілюстровано на рис. 2. / Рис. 2. Порядок обходу вершин графа при пошуку у глибину. Алгоритм перебору в глибину полягає в наступному. 1. Розкривається початкова вершина, відповідна початкового стану. 2. Розкривається перша вершина, що отримується в результаті розкриття початкової. Ставиться покажчик вершини. 3. Якщо ця вершина розкривається, то наступною буде розкриватися знову породжена вершина. Якщо ж вершина не розкривається, то процес повертається в попередню вершину. 4. Після отримання цільової вершини процес розкриття закінчується і за вказівниками будується шлях, що веде до кореня. Відповідні дугам (їх послідовний перелік) оператори утворюють рішення задачі. 5. Якщо для заданої глибини розкриття цільова вершина не знаходиться, то весь процес повторюється знову, а в якості нової вершини розглядається сама ліва з отриманих на попередньому етапі. Для виконання роботи було написано програму в середовищі Visual Studio 2015 мовою C#. Дана програмна реалізація алгоритму демонструє процес знаходження шляху в графі за допомогою алгоритму пошуку в глибину з порядком обходу: зліва направо та справа...